Randomness extractors and error correcting codes are fundamental objects incomputer science. Recently, there have been several natural generalizations ofthese objects, in the context and study of tamper resilient cryptography. Theseare seeded non-malleable extractors, introduced in [DW09]; seedlessnon-malleable extractors, introduced in [CG14b]; and non-malleable codes,introduced in [DPW10]. However, explicit constructions of non-malleable extractors appear to behard, and the known constructions are far behind their non-tamperedcounterparts. In this paper we make progress towards solving the above problems. Ourcontributions are as follows. (1) We construct an explicit seeded non-malleable extractor for min-entropy$k \geq \log^2 n$. This dramatically improves all previous results and gives asimpler 2-round privacy amplification protocol with optimal entropy loss,matching the best known result in [Li15b]. (2) We construct the first explicit non-malleable two-source extractor formin-entropy $k \geq n-n^{\Omega(1)}$, with output size $n^{\Omega(1)}$ anderror $2^{-n^{\Omega(1)}}$. (3) We initiate the study of two natural generalizations of seedlessnon-malleable extractors and non-malleable codes, where the sources or thecodeword may be tampered many times. We construct the first explicitnon-malleable two-source extractor with tampering degree $t$ up to$n^{\Omega(1)}$, which works for min-entropy $k \geq n-n^{\Omega(1)}$, withoutput size $n^{\Omega(1)}$ and error $2^{-n^{\Omega(1)}}$. We show that we canefficiently sample uniformly from any pre-image. By the connection in [CG14b],we also obtain the first explicit non-malleable codes with tampering degree $t$up to $n^{\Omega(1)}$, relative rate $n^{\Omega(1)}/n$, and error$2^{-n^{\Omega(1)}}$.
展开▼
机译：随机性提取器和纠错码是计算机科学中的基本对象。近来，在篡改弹性密码学的背景下和研究中，已经有这些对象的几种自然概括。这些是在[DW09]中引入的播种的非易碎提取器； [CG14b]中介绍的无籽非可萃取提取器；以及在[DPW10]中引入的不可恶意代码。然而，不可恶意提取的显式构造似乎很难，并且已知构造远远落后于其不可篡改的对手。在本文中，我们在解决上述问题方面取得了进展。我们的贡献如下。 （1）我们为最小熵$ k \ geq \ log ^ 2 n $构造了一个显式种子非恶意提取器。这极大地改善了所有先前的结果，并提供了具有最佳熵损失的更简单的两轮隐私放大协议，与[Li15b]中最著名的结果相匹配。 （2）我们构造了第一个显式不可恶意的两源提取器，形式为熵-$ k \ geq nn ^ {\ Omega（1）} $，输出大小为$ n ^ {\ Omega（1）} $ anderror $ 2 ^ {-n ^ {\ Omega（1）}} $。 （3）我们开始研究无种子非可恶意提取程序和不可恶意代码的两种自然概括，其中源或代码字可能会被多次篡改。我们构造了第一个显式不可篡改的两源提取器，其篡改程度为$ t $至$ n ^ {\ Omega（1）} $，适用于最小熵$ k \ geq nn ^ {\ Omega（1）} $，输出大小为$ n ^ {\ Omega（1）} $，错误为$ 2 ^ {-n ^ {\ Omega（1）}} $。我们证明了我们可以有效地从任何原像中进行统一采样。通过[CG14b]中的连接，我们还获得了第一个显式不可篡改代码，其篡改程度为$ t $ up至$ n ^ {\ Omega（1）} $，相对比率为$ n ^ {\ Omega（1）} / n $和错误$ 2 ^ {-n ^ {\ Omega（1）}} $。
展开▼
